﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using ComputerEngine;

namespace Daphne.MoveHelperWrapper
{
    internal static class EngineMoveHelper
    {
        private class Pos
        {
            public Position Position;
            public eFigure FigureType;
        }

        /// <summary>
        /// Static constructor
        /// </summary>
        static EngineMoveHelper()
        {
            // calculate LSBArray values
            for (uint i = 0; i < 256; i++)
            {
                if ((i & 1) != 0) { LSBArray[i] = 0; continue; }
                if ((i & 2) != 0) { LSBArray[i] = 1; continue; }
                if ((i & 4) != 0) { LSBArray[i] = 2; continue; }
                if ((i & 8) != 0) { LSBArray[i] = 3; continue; }
                if ((i & 16) != 0) { LSBArray[i] = 4; continue; }
                if ((i & 32) != 0) { LSBArray[i] = 5; continue; }
                if ((i & 64) != 0) { LSBArray[i] = 6; continue; }
                if ((i & 128) != 0) { LSBArray[i] = 7; continue; }
                LSBArray[i] = -1;
            }
        }

        #region Start Move Computation Helper Methods

        /// <summary>
        /// Game History Model Conversion
        /// </summary>
        internal static OutputBitBoard[] ConvertMoveHistory(GameStateConfig config)
        {
            List<OutputBitBoard> list = new List<OutputBitBoard>();

            OutputBitBoard obb;
            foreach (var bb in config.GameHistory)
            {
                obb = new OutputBitBoard();
                obb.wm = bb.WM;
                obb.wk = bb.WK;
                obb.bm = bb.BM;
                obb.bk = bb.BK;

                list.Add(obb);
            }

            return list.ToArray();

        }

        #endregion


        /// <summary>
        /// The current checkersboard state model conversion
        /// </summary>
        internal static CheckersBoard ConvertBoard(GameStateConfig config)
        {
            int boardSize = (int)Math.Sqrt(config.CheckersBoard.Length);

            CheckersBoard board = new CheckersBoard();
            board.Board = new Coordinate[boardSize, boardSize];
            board.BoardSize = (uint)boardSize;

            for (int row = 0; row < boardSize; row++)
                for (int col = 0; col < boardSize; col++)
                {
                    eFigureType dstFigType = eFigureType.Nothing;
                    eFigure srcFigType = config.CheckersBoard[row, col];

                    switch (srcFigType)
                    {
                        case eFigure.WhiteMan:
                            dstFigType = eFigureType.WhiteMan;
                            break;
                        case eFigure.WhiteKing:
                            dstFigType = eFigureType.WhiteKing;
                            break;
                        case eFigure.BlackMan:
                            dstFigType = eFigureType.BlackMan;
                            break;
                        case eFigure.BlackKing:
                            dstFigType = eFigureType.BlackKing;
                            break;
                    }

                    board.Board[row, col] = new Coordinate(row, col, dstFigType);
                }

            return board;
        }


        #region Move Conversion From Engine
        

        /// <summary>
        /// The main API method for converting move from the internal engine to the container classes
        /// </summary>
        /// <param name="bb"></param>
        /// <param name="config"></param>
        /// <returns></returns>
        internal static List<Position> Convert(OutputBitBoard bb, GameStateConfig config)
        {
            int boardSize = (int)Math.Sqrt(config.CheckersBoard.Length);
            // convert positions
            List<Pos> posList = ConvertPositions(bb, boardSize);

            // find start and end position
            Position startPosition, endPosition;
            FindStartEndPosition(bb, config, out startPosition, out endPosition);
            Pos startPos = null; Pos endPos = null;
            List<Position> pathList = null; 

            if (startPosition == Position.Empty) // if circular move
            {
                // get all moves from given STM
                List<Pos> figureList = GetAllFigures(config.WhiteToMove ? eColor.White : eColor.Black, config);

                // iterate through all figures
                bool found = false;
                foreach (var pos in figureList)
                {
                    // set start and end position
                    startPos = pos;
                    endPos = pos;

                    // try to find the path
                    pathList = FindPath(startPos, endPos, posList, config);
                    if (pathList != null)
                    {
                        found = true;
                        break;
                    }
                }

                if (!found)
                    throw new ApplicationException("No figure for circular jump.");
            }
            else
            {
                eColor stm = config.WhiteToMove ? eColor.White : eColor.Black;

                // find starting position
                startPos = posList.FirstOrDefault(i => i.Position == startPosition 
                    && i.FigureType.FigureColor() == stm);
                if (startPos == null)
                    throw new ApplicationException("Error finding starting position.");

                // find end position
                endPos = posList.FirstOrDefault(i => i.Position == endPosition
                       && i.FigureType.FigureColor() == stm);
                if (endPos == null)
                    throw new ArgumentNullException("Error finding ending position.");

                // remove source and target
                posList.Remove(startPos);
                posList.Remove(endPos);

                // find path
                pathList = FindPath(startPos, endPos, posList, config);
            }

            List<Position> result = new List<Position>();
            result.Add(startPos.Position);
            result.AddRange(pathList);
            result.Add(endPos.Position);

            return result;
        }

        /// <summary>
        /// Sorts the move positions according the move path
        /// </summary>
        private static List<Position> FindPath(Pos startPos, Pos endPos, List<Pos> inList, GameStateConfig config)
        {
            // clear moving figure
            config.ClearField(startPos.Position.Row, startPos.Position.Col);

            // find path
            var path = ProbePath(startPos.Position, endPos.Position, inList, config);
            
            // restore the CB situation
            config.FullRestore();

            return path;
        }

        private struct SRemovedFigure
        {
            public int Row;
            public int Col;
            eFigure Figure;
        }

        private static List<Position> ProbePath(Position startPos, Position endPos, List<Pos> argJumpedFigures, GameStateConfig config)
        {
            // initialization
            List<Position> path = new List<Position>();
            List<Pos> jumpedFigures = new List<Pos>();
            jumpedFigures.AddRange(argJumpedFigures);          

            // starting position
            Position lastPos = startPos;

            // iterate through all jumped figures
            while (jumpedFigures.Count > 1)
            {
                // find the nearest opponent figure that is captured
                Position jumpedFigPos = Position.Empty;
                Pos  jumpedFig = null;
                int moveLength = int.MaxValue;

                // iterate all captured figures
                foreach (var itemFig in jumpedFigures)
                {
                    // is the captured figure on the diagonal
                    if (itemFig.Position.IsDiagonal(lastPos))
                    {
                        int length = Math.Abs(itemFig.Position.Row - lastPos.Row);
                        // if it is shortest jump, record capture
                        if (length < moveLength)
                        {
                            jumpedFigPos = itemFig.Position;
                            jumpedFig = itemFig;
                            moveLength = length;
                        }
                    }
                }
                // do check we have found the figure, if not, the path is wrong
                if (jumpedFigPos == Position.Empty)
                    return null;

                // remove the captured figure and find the diagonal
                jumpedFigures.Remove(jumpedFig);
                enumDiagonalDir direction = lastPos.GetDiagonalDir(jumpedFigPos);

                // remove jumped figure from the field
                config.ClearField(jumpedFigPos.Row, jumpedFigPos.Col);
                
                List<Position> potentialCaptures = new List<Position>();
                Position jumpField = jumpedFigPos;
                bool bFound = false;
                // move to the end of checkers board
                while (IsOutsideBoard(config, jumpField) == false)
                {
                    // move one field
                    jumpField = jumpField.GetNextField(direction);

                    // check, if not outside board
                    if (IsOutsideBoard(config, jumpField))
                        break;

                    // check the field is empty
                    if (config.CheckersBoard[jumpField.Row, jumpField.Col] != eFigure.None)
                        break;

                    // check all captured figures
                    foreach (var itemFig in jumpedFigures)
                    {
                        // if possible capture field for continuing jump found
                        if (itemFig.Position.IsDiagonal(jumpField))
                        {
                            // check, if there is empty field for jump
                            enumDiagonalDir dir = jumpField.GetDiagonalDir(itemFig.Position);
                            Position captureField = itemFig.Position.GetNextField(dir);

                            // if empty space for landing after capture
                            if (config.CheckersBoard[captureField.Row, captureField.Col] == eFigure.None)
                            {
                                bFound = true;
                                potentialCaptures.Add(jumpField);
                            }
                        }
                    }
                }

                // check if potential capture found
                if (bFound)
                {
                    // if one record
                    if (potentialCaptures.Count == 1)
                    {
                        // if found, record the capture path
                        path.Add(potentialCaptures[0]);
                        lastPos = potentialCaptures[0];

                    }
                    else
                    {
                        // check the path
                        foreach (var potentialField in potentialCaptures)
                        {

                            var subPath = ProbePath(potentialField, endPos, jumpedFigures, config);

                            // if sub path found
                            if (subPath != null)
                            {
                                path.Add(potentialField);
                                path.AddRange(subPath);
                                // path.Add(endPos);
                                return path;
                            }
                        }

                        // no sub path found, error
                        return null;
                    }
                }
                else
                {
                    // selected path is wrong
                    return null; 
                }
            }

            // return final path
            return path;
        }

        /// <summary>
        /// Returns all figures for given STM
        /// </summary>
        private static List<Pos> GetAllFigures(eColor stmColor, GameStateConfig config)
        {
            List<Pos> outputList = new List<Pos>();
            int boardSize = (int)Math.Sqrt(config.CheckersBoard.Length);

            for (int row = 0; row < boardSize; row++)
            {
                for (int col = 0; col < boardSize; col++)
                {
                    eFigure fig = config.CheckersBoard[row, col];
                    if (fig != eFigure.None) // if not empty field
                    {
                        if (fig.FigureColor() == stmColor) // if figure of given STM
                        {
                            // create record structure
                            Pos pos = new Pos();
                            pos.Position = new Position(row, col);
                            pos.FigureType = fig;

                            outputList.Add(pos);                           
                        }
                    } // if
                } // for
            } // for

            return outputList;
        }


        /// <summary>
        /// Checks, the field is outside board
        /// </summary>
        private static bool IsOutsideBoard(GameStateConfig config, Position pos)
        {
            int boardSize = (int)Math.Sqrt(config.CheckersBoard.Length);

            if (pos.Row < 0 || pos.Col < 0)
                return true;
            if (pos.Row >= boardSize || pos.Col >= boardSize)
                return true;

            return false;
        }

        private static void FindStartEndPosition(OutputBitBoard move, GameStateConfig config, 
                        out Position startPos, out Position endPos)
        {
            int boardSize = (int)Math.Sqrt(config.CheckersBoard.Length);

            // set initial values
            startPos = Position.Empty;
            endPos = Position.Empty;

            // get the last board situation
            if (config.GameHistory.Length == 0)
                throw new ApplicationException("No game history");
            
            // get the last board situation
            BitBoard board = config.GameHistory[config.GameHistory.Length - 1];

            // get STM occupied fields
            ulong occupiedBoard = config.WhiteToMove ? board.WM | board.WK : board.BM | board.BK;
            ulong occupiedMove = config.WhiteToMove ? move.wm | move.wk : move.bm | move.bk;

            // get starting position pattern and the field index
            ulong startPattern = occupiedBoard & occupiedMove;
            int startIndex = LSB(startPattern);
            if (startIndex < 0)
                return; // it is circular move, no method here to find out

            // calculate end position index
            ulong occupiedBoardMoveDone = occupiedBoard ^ occupiedMove;
            ulong endPattern = occupiedBoardMoveDone & occupiedMove;
            int endIndex = LSB(endPattern);
            if (endIndex < 0) // if not bit set, then it is circular move
                throw new ApplicationException("Error ending position.");

            // convert indexes to positions
            startPos = ConvertPosition(startIndex, boardSize);
            endPos = ConvertPosition(endIndex, boardSize);
        }

        /// <summary>
        /// Converts the bitboard record to position coordinates
        /// </summary>
        private static List<Pos> ConvertPositions(OutputBitBoard bb, int boardSize)
        {
            List<Pos> list = new List<Pos>();

            int shift = 0;

            for (int row = 0; row < boardSize; row++)
                for (int col = 0; col < boardSize; col++)
                {
                    if (new Position(row, col).GetFieldColor() == eColor.Black)
                    {
                        Position position = new Position(row, col);

                        // needed list, end position may be at the same square
                        // and the captured figure
                        List<eFigure> fig = new List<eFigure>();

                        if ((bb.wm & ((ulong)1 << shift)) != 0)
                            fig.Add(eFigure.WhiteMan);
                        if ((bb.wk & ((ulong)1 << shift)) != 0)
                            fig.Add(eFigure.WhiteKing);
                        if ((bb.bm & ((ulong)1 << shift)) != 0)
                            fig.Add(eFigure.BlackMan);
                        if ((bb.bk & ((ulong)1 << shift)) != 0)
                            fig.Add(eFigure.BlackKing);

                        if (fig.Count > 0)
                        {
                            foreach (var f in fig)
                            {
                                Pos pos = new Pos();
                                pos.Position = position;
                                pos.FigureType = f;
                                list.Add(pos);
                            }
                        }

                        shift++;
                    }
                }

            return list;
        }

        /// <summary>
        /// Creates the position structure out of index
        /// </summary>
        private static Position ConvertPosition(int index, int boardSize)
        {
            boardSize /= 2;
            int row = index / boardSize;
            int col = index % boardSize;

            if (row % 2 == 0)
                col = col * 2;
            else
                col = col * 2 + 1;

            return new Position(row, col);
        }

        /// <summary>
        /// Finds out the least significant bit in given value
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        private static int LSB(ulong x)
        {
            if ((x & 0x00000000000000FF) != 0)
                return (LSBArray[x & 0x000000FF]);
            if ((x & 0x000000000000FF00) != 0)
                return (LSBArray[(x >> 8) & 0x000000FF] + 8);
            if ((x & 0x0000000000FF0000) != 0)
                return (LSBArray[(x >> 16) & 0x000000FF] + 16);
            if ((x & 0x00000000FF000000) != 0)
                return (LSBArray[(x >> 24) & 0x000000FF] + 24);
            if ((x & 0x000000FF00000000) != 0)
                return (LSBArray[(x >> 32) & 0x000000FF] + 32);
            if ((x & 0x0000FF0000000000) != 0)
                return (LSBArray[(x >> 40) & 0x000000FF] + 40);
            if ((x & 0x00FF000000000000) != 0)
                return (LSBArray[(x >> 48) & 0x000000FF] + 48);
            if ((x & 0xFF00000000000000) != 0)
                return (LSBArray[(x >> 56) & 0x000000FF] + 56);
            return -1;
        }


        /// <summary>
        /// Values for calculating LSB
        /// </summary>
        static int[] LSBArray = new int[256];

        #endregion
    }
}
